/********************************
 * Robinson Matrix Algorithm
 *
 * Copyright (C) 2009 CNRS
 * Author : Florent AVELLANEDA, Eugen CEPOI
 * Algorithm design : Victor CHEPOI, Morgan SESTON ( http://www.lif-sud.univ-mrs.fr/%7Echepoi/robinson_chepoi_seston.pdf )
 * 
 *
 * All rights reserved.
 *
 *   This file is part of Robinson Matrix Algorithm.
 *
 *   Robinson Matrix Algorithm is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   Robinson Matrix Algorithm is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with Robinson Matrix Algorithm.  If not, see <http://www.gnu.org/licenses/>.
 *
 ***********************************************************************************/
#ifndef GRAPHS_H_
#define GRAPHS_H_

class Matrix;
class PartialOrder;
namespace SAT
{
    class Var;
    class SAT;
}
#include <set>
#include <vector>

namespace Graphs
{

    /** 
     * @brief It's the main function concerning the graphs. Inside we call all the functions working
     * on the graphs and the partitioning.
     * 
     * @param m input
     * @param epsilon input
     * @param X input
     * @param X_m output (X-)
     * @param X_p output (X+)
     * @param order_m output (<=-)
     * @param order_p output (<=+)
     * 
     * @return true if there is a solution for this sub problem
     */
    bool partitionAndSort(Matrix *m, double epsilon, unsigned int leftBoundHole1, unsigned int rightBoundHole1, 
            unsigned int leftBoundHole2, unsigned int rightBoundHole2, std::set<unsigned int> &Xij, 
            std::vector<std::set<unsigned int> > &cellsOfOL, std::set<unsigned int> &X_m, 
            std::set<unsigned int> &X_p, std::vector<PartialOrder*> &Cij_m, 
            std::vector<PartialOrder*> &Cij_p, std::vector<unsigned int> &cellsOrder_m, 
            std::vector<unsigned int> &cellsOrder_p);

    /**
     * @brief Constructs the graph S
     */
    void graphS(std::vector<std::set<unsigned int> > &S, std::vector<unsigned int> &X, 
            std::vector<double> &d, double epsilon, Matrix *m);

    /**
     * @brief Constructs the graph L
     */
    void graphL(std::vector<std::set<unsigned int> > &L, std::vector<unsigned int> &X, 
            std::vector<double> &d, double epsilon,Matrix *m);

    /**
     * @brief Constructs the partition of L into blocks
     */
    void partitionL(std::vector<unsigned int> &blockOfL, std::vector<std::set<unsigned int> > &L);

    /**
     * @brief Constructs the L oriented graph
     */
    void graphOL(std::vector<std::set<unsigned int> > &OL, std::vector<unsigned int> &X, 
            std::vector<unsigned int> &blockOfL, std::vector<std::set<unsigned int> > &L, 
            std::vector<double> &d, double epsilon, Matrix *m );

    /**
     * @brief Constructs the cells of the L oriented graph
     */
    void cellsOL(std::vector<std::set<unsigned int> > &L, std::vector<std::set<unsigned int> > &OL,
            std::vector<std::set<unsigned int> > &cellsOfOL, std::vector<unsigned int> &xCellsOfOl );

    /**
     * @brief Constructs the graph psy
     */
    void graphPsy(std::vector<std::set<unsigned int> > &psy, std::vector<std::set<unsigned int> > &cellsOfOL, 
            std::vector<unsigned int> xCellsOfOl, std::vector<unsigned int> &blockOfL, 
            std::vector<std::set<unsigned int> > &S, std::vector<std::set<unsigned int> > &L, 
            std::vector<unsigned int> &X, std::vector<double> &d, double epsilon, Matrix *m );

    /**
     * @brief Constructs and solves the 2-sat problem
     */
    bool sat( std::vector< SAT::Var > &vVar, std::vector<std::set<unsigned int> > &Gij, std::vector<std::set<unsigned int> > &G1, std::vector<std::set<unsigned int> > &G2, 
            std::vector<std::set<unsigned int> > &G3, std::vector<std::set<unsigned int> > &cellsOfOL,
            std::vector<unsigned int> &clusterOfPsy, std::vector<std::set<unsigned int> > &clusters, 
            std::vector<unsigned int> &X, std::vector<std::set<unsigned int> > &L, 
            std::vector<double> &d, double epsilon, Matrix *m, unsigned int leftBoundHole1,
            unsigned int rightBoundHole1, unsigned int leftBoundHole2, unsigned int rightBoundHole2);

    bool isG2(unsigned int i, unsigned int j, std::vector<std::set<unsigned int> > &cellsOfOL, 
            std::vector<double> &d, double epsilon);

    bool isG3(unsigned int i, unsigned int j, std::vector<std::set<unsigned int> > &cellsOfOL,
            std::vector<double> &d, double epsilon, std::vector<unsigned int> &X, 
            std::vector<std::set<unsigned int> > &L, Matrix *m);

    void createOmega( std::set< std::pair<unsigned int, unsigned int> > &omega, std::vector<std::set<unsigned int> > &G1,
            std::vector<std::set<unsigned int> > &G2, std::vector<std::set<unsigned int> > &G3 );

    /**
     * @brief Constructs the partitions : creation of sub matrices with the elements of a cell,
     *  creation of a partial order for them, definition of a total order on the cells
     */
    void partition(std::set<unsigned int> &X_m, std::set<unsigned int> &X_p, std::vector<std::set<unsigned int> > &Gij,
            std::vector<PartialOrder* > &Cij_m, std::vector<PartialOrder* > &Cij_p, unsigned int leftBoundHole1,
            unsigned int rightBoundHole1, unsigned int leftBoundHole2, unsigned int rightBoundHole2, 
            std::vector< SAT::Var > &vVar, std::vector<unsigned int> &cellsOrder_m,
            std::vector<unsigned int> &cellsOrder_p, std::vector<std::set<unsigned int> > &cellsOfOL,
            std::vector<unsigned int> &X, std::vector<std::set<unsigned int> > &L, 
            std::vector<double> &d, double epsilon, Matrix *m );

    bool aarrow(unsigned int i, unsigned int j, double epsilon, std::vector<double> &d, 
            std::vector<unsigned int> &X, std::vector<std::set<unsigned int> > &L, Matrix *m);

    bool twinClusters( std::vector<unsigned int > &clusterOfPsy, unsigned int a, unsigned int b );

    void calculateDx(std::vector<double> &d, std::vector<unsigned int> &X, Matrix *m);

};

#endif /*GRAPHS_H_*/
